কার্নফ ম্যাপ (Karnaugh Map - K-map)
কার্নফ ম্যাপ (K-map) হল ডিজিটাল লজিক সার্কিট ডিজাইনের একটি সরঞ্জাম যা বুলিয়ান অভিব্যক্তি (Boolean expressions) সরলীকরণের জন্য ব্যবহৃত হয়। এটি মূলত কম্বিনেশনাল লজিক সার্কিটের বুলিয়ান ফাংশন সহজতর করার জন্য একটি ভিজ্যুয়াল পদ্ধতি। K-map, সত্যক সারণির উপর ভিত্তি করে কাজ করে এবং বুলিয়ান সমীকরণগুলিকে সহজে সামঞ্জস্যপূর্ণ ফর্মে নিয়ে আসতে সাহায্য করে।
K-map এর বৈশিষ্ট্য
- দ্রুত এবং সহজ সরলীকরণ: K-map বুলিয়ান এক্সপ্রেশন সরলীকরণ দ্রুত এবং সহজভাবে করতে সহায়ক।
- দৃশ্যমান গ্রুপিং: এতে ম্যানুয়ালি গ্রুপিং এর মাধ্যমে টার্ম সরলীকরণ করা যায়।
- কম বিটের জন্য কার্যকর: ২, ৩ বা ৪ ভেরিয়েবল যুক্ত ফাংশনের জন্য অত্যন্ত কার্যকর এবং বড় সিস্টেমেও ব্যবহার করা যায়।
K-map এর কাঠামো
K-map সাধারণত ২, ৩, বা ৪টি ভেরিয়েবল নিয়ে তৈরি করা হয়, এবং প্রতিটি সেলের অবস্থান একটি বিশেষ বাইনারি মান নির্দেশ করে।
- ২ ভেরিয়েবল K-map: এতে ৪টি সেল থাকে।
- ৩ ভেরিয়েবল K-map: এতে ৮টি সেল থাকে।
- ৪ ভেরিয়েবল K-map: এতে ১৬টি সেল থাকে।
K-map তৈরি প্রক্রিয়া
১. প্রথমে সত্যক সারণি (Truth Table) তৈরি করুন: বুলিয়ান ফাংশনের ইনপুট এবং আউটপুট সম্পর্কে জানতে সত্যক সারণি তৈরি করতে হয়।
২. K-map এ মান বসানো: সত্যক সারণি অনুযায়ী K-map এ ১ ও ০ এর মান বসাতে হয়। সাধারণত আউটপুট ১ হলে সেটিকে K-map এ চিহ্নিত করা হয়।
৩. গ্রুপিং: K-map এর মানগুলোকে গোষ্ঠীবদ্ধ করা হয় (যেমন ১, ২, ৪ বা ৮ টি কোষ) যাতে সহজ সরলীকরণ করা যায়। গোষ্ঠীগুলি ভেরিয়েবল সংযোজন বা বিয়োজনের নিয়ম মেনে তৈরি করতে হয়।
৪. সরলীকৃত এক্সপ্রেশন তৈরি: গ্রুপ করা কোষগুলো থেকে সরলীকৃত বুলিয়ান এক্সপ্রেশন তৈরি করা হয়।
উদাহরণ: ৩ ভেরিয়েবল K-map
তিনটি ভেরিয়েবল (A, B, C) সহ K-map
ধরুন, একটি বুলিয়ান ফাংশন F = Σ(1, 3, 5, 7)
- ৩ ভেরিয়েবল K-map এ ৮টি সেল থাকবে, যার প্রতিটি একটি ভিন্ন বাইনারি মান নির্দেশ করে।
- F = Σ(1, 3, 5, 7) অনুসারে এই কোষগুলিতে মান ১ বসানো হবে।
| AB\C | 0 | 1 |
|---|---|---|
| 00 | 0 | 1 |
| 01 | 1 | 0 |
| 11 | 1 | 0 |
| 10 | 0 | 1 |
এরপর গ্রুপিং করে সরলীকৃত ফর্মে প্রকাশ করা হয়, যেমনঃ F=AB‾+BCF = A \overline{B} + B CF=AB+BC
K-map এর ব্যবহার
- ডিজিটাল লজিক সার্কিট ডিজাইন: কম বিটের কম্বিনেশনাল লজিক সার্কিটের সরলীকরণ।
- আবশ্যকীয় ইকুয়েশন সরলীকরণ: বুলিয়ান এক্সপ্রেশন কমিয়ে সিস্টেম ডিজাইন সহজ করা।
- ত্রুটি নির্ধারণ ও সংশোধন: কনট্রোল সার্কিট ও কমিউনিকেশন সিস্টেমে ত্রুটি সংশোধনের জন্য।
উদাহরণ: যদি আপনি এমন একটি সার্কিট ডিজাইন করতে চান যেখানে আউটপুট তখনই ১ হবে যখন নির্দিষ্ট ইনপুট কম্বিনেশন পূরণ হবে, K-map সহজে সরলীকৃত লজিক দিয়ে এটি ডিজাইন করতে সহায়ক।
কার্নফ ম্যাপের ধারণা এবং এর ব্যবহার
কার্নফ ম্যাপ (Karnaugh Map বা K-Map) একটি ভিজ্যুয়াল টুল যা বুলিয়ান এক্সপ্রেশনকে সহজতর করতে ব্যবহার করা হয়। এটি সুনির্দিষ্ট নিয়ম এবং গ্রিড-ভিত্তিক ম্যাপের সাহায্যে ভ্যারিয়েবলগুলোর মধ্যে সম্পর্ক নির্ধারণ করে। কার্নফ ম্যাপ লজিক ডিজাইনে সরলীকরণের মাধ্যমে ডিজিটাল সার্কিটের জটিলতা কমাতে সাহায্য করে।
কার্নফ ম্যাপের ধারণা
কার্নফ ম্যাপ মূলত একটি টেবিল বা গ্রিড আকারে উপস্থাপিত হয়, যা লজিক ভ্যারিয়েবলের প্রতিটি মুন টার্ম (minterm) বা ম্যাক্স টার্মকে প্রতিনিধিত্ব করে। প্রতিটি সেলে ০ বা ১ থাকে, যা নির্দিষ্ট লজিক কম্বিনেশনের আউটপুটকে নির্দেশ করে। গ্রিডের কোষগুলোতে পার্শ্ববর্তী কোষগুলোর মধ্যে এক বা একাধিক ভ্যারিয়েবলের পার্থক্য থাকে। এই টেবিল বা গ্রিডে সংশ্লিষ্ট কোষগুলো গ্রুপিং করে সরলীকৃত বুলিয়ান এক্সপ্রেশন তৈরি করা হয়।
কার্নফ ম্যাপের গঠন
১. ভ্যারিয়েবলের সংখ্যা অনুযায়ী গ্রিড সাইজ নির্ধারণ:
- ২ ভ্যারিয়েবল থাকলে ২x২ গ্রিড।
- ৩ ভ্যারিয়েবল থাকলে ২x৪ গ্রিড।
- ৪ ভ্যারিয়েবল থাকলে ৪x৪ গ্রিড।
২. গ্রে কোড ব্যবহার: কোষগুলোর মধ্যে একটিমাত্র ভ্যারিয়েবলের পরিবর্তন ঘটে যেন গ্রুপিং প্রক্রিয়ায় সহজে সরলীকরণ করা যায়। অর্থাৎ, গ্রে কোড সিকোয়েন্স (00, 01, 11, 10) ব্যবহার করে কোষগুলোর অর্ডার নির্ধারণ করা হয়।
কার্নফ ম্যাপের ব্যবহার
কার্নফ ম্যাপ ব্যবহারের মূল লক্ষ্য হলো একটি জটিল লজিক ফাংশনকে যতটা সম্ভব সরল করা, যাতে গেটের সংখ্যা কমে এবং সার্কিট ডিজাইন সহজ হয়। এর ব্যবহার সাধারণত নিম্নরূপ:
১. লজিক ফাংশনের সরলীকরণ
- কার্নফ ম্যাপে সত্য টেবিলের সাহায্যে ইনপুট কম্বিনেশনের আউটপুটগুলো বসানো হয়।
- প্রতিটি ১ বা ০ মানযুক্ত কোষগুলোকে নিকটবর্তী কোষগুলোর সাথে গ্রুপিং করে একটি বড় লজিক টার্মে একত্রিত করা হয়।
- গ্রুপিংয়ের মাধ্যমে সরলীকৃত এক্সপ্রেশন পাওয়া যায়, যা কম সংখ্যক লজিক গেটের মাধ্যমে বাস্তবায়ন করা যায়।
২. গ্রুপিং নিয়ম
- কোষগুলোতে সন্নিহিত ১ বা ০ সমূহ গ্রুপ আকারে একত্রিত করতে হয়।
- গ্রুপগুলো ১, ২, ৪, ৮, ইত্যাদি কোষের সমন্বয়ে হতে পারে।
- প্রতিটি গ্রুপের জন্য সরলীকৃত বুলিয়ান এক্সপ্রেশন লেখা হয়।
৩. কমপ্লিমেন্টেড টার্ম অপসারণ
- গ্রুপিংয়ের মাধ্যমে যে এক্সপ্রেশন পাওয়া যায়, তাতে ভ্যারিয়েবলের কমপ্লিমেন্টেড বা নন-কমপ্লিমেন্টেড ফর্মগুলো একত্রিত হয়। এতে ফলাফল সরল হয়।
উদাহরণ
ধরা যাক, একটি তিন-বিট ইনপুট (A, B, C) রয়েছে এবং সত্য টেবিল অনুযায়ী আউটপুট (F) পাওয়া যায়।
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
কার্নফ ম্যাপ ব্যবহার করে আমরা ১ সমূহকে গ্রুপিং করতে পারি এবং সরলীকৃত ফাংশন পাই।
কার্নফ ম্যাপের সুবিধাসমূহ
- সহজ সরলীকরণ: ম্যানুয়ালি গণনা ছাড়াই গ্রাফিকালভাবে সরলীকরণ করা যায়।
- গেটের সংখ্যা হ্রাস: সরলীকরণের ফলে কম গেটে কাজ সম্পাদন সম্ভব, যা খরচ ও স্থান বাঁচায়।
- এমনকি জটিল সার্কিটেও ব্যবহারযোগ্য: চার বা পাঁচ ভ্যারিয়েবলের উপর ভিত্তি করে সরলীকরণ করা সম্ভব।
কার্নফ ম্যাপ ডিজিটাল ইলেকট্রনিক্স এবং ডিজিটাল লজিক ডিজাইনে অত্যন্ত কার্যকরী সরঞ্জাম।
বুলিয়ান ফাংশন সরলীকরণে K-map এর প্রয়োগ
Karnaugh Map (K-map) বুলিয়ান ফাংশন সরলীকরণে খুব কার্যকরী একটি পদ্ধতি, কারণ এটি ভিজ্যুয়ালি গ্রুপিং এর মাধ্যমে ফাংশনকে সহজভাবে সরলীকৃত আকারে প্রকাশ করতে সহায়ক। এটি সত্যক সারণির মানগুলো নিয়ে গোষ্ঠীবদ্ধ করে একটি সংক্ষিপ্ত লজিক এক্সপ্রেশন তৈরি করে যা ডিজিটাল সার্কিট ডিজাইনে কম সংখ্যক গেট ব্যবহার করে তৈরি করা যায়।
K-map সরলীকরণের ধাপসমূহ
১. সত্যক সারণি থেকে K-map তৈরি:
সত্যক সারণি অনুযায়ী প্রতিটি আউটপুট ১ এর মান K-map এর সেলে বসান। একটি N-ভেরিয়েবল যুক্ত K-map এ ২^N টি সেল থাকবে।
২. K-map এ গ্রুপিং:
K-map এ যে কোষগুলোতে মান ১ আছে, সেগুলোকে একত্রিত করে গোষ্ঠীবদ্ধ করুন। প্রতিটি গ্রুপে ১, ২, ৪, বা ৮ টি কোষ থাকতে পারে (২^n এর কোনো ঘাত)। এই গোষ্ঠীগুলি সন্নিহিত হওয়া উচিত এবং চারপাশের কোষের মতো হতে পারে (যেমন, উপরের কোষ নিচের সাথে এবং বাম পাশের কোষ ডান পাশের সাথে সন্নিহিত ধরা হয়)।
৩. বুলিয়ান এক্সপ্রেশন লেখা:
প্রতিটি গ্রুপকে একটি বুলিয়ান টার্ম হিসেবে প্রকাশ করুন, যেখানে ওই গ্রুপের জন্য কমন ভেরিয়েবলগুলোকে অন্তর্ভুক্ত করে সরলীকৃত ফর্মে লেখা হয়। একক গ্রুপের জন্য কমন ভেরিয়েবলগুলো “AND” (পণ্য) অপারেটর ব্যবহার করে লেখা হয় এবং প্রতিটি গ্রুপ “OR” (যোগ) অপারেটর দিয়ে যুক্ত হয়।
উদাহরণ: ৩ ভেরিয়েবল বুলিয়ান ফাংশন সরলীকরণে K-map প্রয়োগ
ধরুন, একটি বুলিয়ান ফাংশন F(A,B,C)=Σ(1,3,5,7)F(A, B, C) = Σ(1, 3, 5, 7)F(A,B,C)=Σ(1,3,5,7)।
প্রথমে, আমরা ৩ ভেরিয়েবলের জন্য K-map তৈরি করবো, যেখানে ৮টি সেল থাকবে। এরপর ১ অনুযায়ী কোষগুলিকে পূরণ করা হবে।
৩-ভেরিয়েবল K-map
| AB\C | 0 | 1 |
|---|---|---|
| 00 | 0 | 1 |
| 01 | 1 | 0 |
| 11 | 1 | 0 |
| 10 | 0 | 1 |
এই K-map এ যে কোষগুলোতে ১ আছে, সেগুলিকে গ্রুপিং করা হবে:
- কোষ (1, 3) এবং (5, 7) একসাথে গ্রুপ করা যায়।
- গ্রুপগুলিকে সংক্ষিপ্ত আকারে লিখলে, সরলীকৃত ফাংশনটি দাঁড়াবে F=AB‾+BCF = A \overline{B} + BCF=AB+BC
আরেকটি উদাহরণ: ৪ ভেরিয়েবল বুলিয়ান ফাংশন সরলীকরণ
ধরুন, একটি ফাংশন F(W,X,Y,Z)=Σ(0,1,2,5,8,9,10)F(W, X, Y, Z) = Σ(0, 1, 2, 5, 8, 9, 10)F(W,X,Y,Z)=Σ(0,1,2,5,8,9,10)।
১. প্রথমে ৪ ভেরিয়েবল K-map তৈরি করে সেগুলিকে মান ১ দিয়ে পূরণ করুন। ২. কোষগুলোকে ২ বা ৪-এর গ্রুপে গ্রুপিং করুন। ৩. প্রতিটি গ্রুপের জন্য কমন ভেরিয়েবল দেখে সংক্ষিপ্ত বুলিয়ান এক্সপ্রেশন লিখুন।
এই পদ্ধতির মাধ্যমে বড় ফাংশনগুলোকেও সহজভাবে সরলীকৃত আকারে নিয়ে আসা যায় এবং ডিজিটাল সার্কিট ডিজাইনে প্রয়োজনীয় গেট সংখ্যা কমানো যায়।
মেপিং টেকনিক এবং ডোন্ট কেয়ার কন্ডিশন
মেপিং টেকনিক (Mapping Technique) এবং ডোন্ট কেয়ার কন্ডিশন (Don't Care Condition) কার্নফ ম্যাপ (K-Map) সরলীকরণে গুরুত্বপূর্ণ ভূমিকা পালন করে। এদের সাহায্যে জটিল লজিক ফাংশন সরল করতে এবং ডিজিটাল সার্কিটে গেটের সংখ্যা কমিয়ে আনতে সহজ হয়।
মেপিং টেকনিক
মেপিং টেকনিক ব্যবহার করে বুলিয়ান ফাংশনগুলোর সরলীকরণ করা হয়। কার্নফ ম্যাপকে একটি গ্রিডে বিভক্ত করে লজিক টেবিলের বিভিন্ন ইনপুট কম্বিনেশন চিহ্নিত করা হয়, যেখানে প্রতিটি কোষ একটি নির্দিষ্ট আউটপুট মানকে নির্দেশ করে। মেপিংয়ের মাধ্যমে ইনপুটগুলোর মানকে সমন্বিতভাবে সহজ এক্সপ্রেশন আকারে প্রকাশ করা যায়।
মেপিং প্রক্রিয়া
১. কার্নফ ম্যাপের সেল পূরণ: কার্নফ ম্যাপে সত্য টেবিল থেকে আউটপুট মানগুলো (১ বা ০) বসানো হয়।
২. গ্রুপিং: ১ বা ০ মানের সন্নিহিত কোষগুলোকে পাওয়ার অফ ২-এর (যেমন ১, ২, ৪, ৮) গুণফলে গ্রুপ করা হয়।
- এক কোষ, দুই কোষ, চার কোষ, আট কোষ ইত্যাদি আকারের গ্রুপ বানানো যায়।
- প্রত্যেক গ্রুপে কোষগুলো পাশাপাশি বা চারদিকে সন্নিহিত হতে হবে।
৩. সরলীকৃত এক্সপ্রেশন বের করা: প্রতিটি গ্রুপের জন্য লজিক এক্সপ্রেশন তৈরি করা হয় এবং এভাবে সরলীকৃত এক্সপ্রেশন পাওয়া যায়।
উদাহরণ
ধরা যাক, তিন-বিট ইনপুট A, B, C আছে এবং আমরা ১ মানবিশিষ্ট কোষগুলোকে গ্রুপিং করে সরলীকৃত ফাংশন বের করতে চাই।
| A | B | C | Output |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
এর থেকে আমরা গ্রুপিং করে সরলীকৃত এক্সপ্রেশন বের করতে পারি।
ডোন্ট কেয়ার কন্ডিশন (Don't Care Condition)
ডিজিটাল লজিক সার্কিটে কিছু ইনপুট কম্বিনেশনে আউটপুট নির্ধারণ করা প্রয়োজন হয় না। এসব অবস্থাকে ডোন্ট কেয়ার কন্ডিশন বলা হয়। এগুলোকে সাধারণত "X" বা "d" দিয়ে চিহ্নিত করা হয়। ডোন্ট কেয়ার কন্ডিশন সরলীকরণের প্রক্রিয়া সহজ করতে সাহায্য করে।
ডোন্ট কেয়ার কন্ডিশন ব্যবহার করে কার্নফ ম্যাপে সরলীকরণে সহায়তা পাওয়া যায় কারণ এদের ১ বা ০ হিসেবে বিবেচনা করে বৃহত্তর গ্রুপ তৈরি করা যায়।
ডোন্ট কেয়ার কন্ডিশনের সুবিধা
১. বৃহত্তর গ্রুপ তৈরি: ডোন্ট কেয়ার কন্ডিশনগুলোকে প্রয়োজন অনুসারে ১ হিসেবে ধরে বড় গ্রুপ তৈরি করা যায়। ২. সরলীকরণ সহজ করা: বড় গ্রুপ তৈরির মাধ্যমে ফাংশন সরল হয় এবং ডিজিটাল সার্কিটে কম সংখ্যক গেট ব্যবহার করা যায়।
উদাহরণ
ধরা যাক, একটি চার-বিট ইনপুট ফাংশন আছে যেখানে কিছু ডোন্ট কেয়ার কন্ডিশন রয়েছে।
| A | B | C | D | Output |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | X |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | X |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | X |
| 0 | 1 | 1 | 1 | 1 |
এখানে ডোন্ট কেয়ার কন্ডিশনগুলোকে ১ হিসেবে ধরে গ্রুপিং করলে সরলীকরণ করা সহজ হয়।
সারসংক্ষেপ
- মেপিং টেকনিক: লজিক ফাংশনকে সহজভাবে গ্রুপিংয়ের মাধ্যমে সরলীকৃত করে এবং ডিজিটাল সার্কিটকে কার্যকরী করে তোলে।
- ডোন্ট কেয়ার কন্ডিশন: এই কন্ডিশনগুলো সরলীকরণে ব্যবহার করে ফাংশন আরও সহজভাবে প্রকাশ করতে সহায়তা করে, যা সার্কিট ডিজাইনকে সহজ ও কম খরচে কার্যকর করে।
এই প্রক্রিয়াগুলো ডিজিটাল ইলেকট্রনিক্সে অত্যন্ত গুরুত্বপূর্ণ কারণ এগুলো ডিজিটাল লজিককে সহজতর করে এবং সার্কিট ডিজাইনের খরচ ও জটিলতা কমায়।
Read more
